import collections
class Solution(object):
    def numSubmatrixSumTarget(self, matrix, target):
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(1, n):
                matrix[i][j] += matrix[i][j - 1]
        ans = 0
        for i in range(n):
            for j in range(i, n):
                now = 0
                d = collections.defaultdict(int)
                d[0] = 1
                for k in range(m):
                    if i == 0:
                        val = matrix[k][j]
                    else:
                        val = matrix[k][j] - matrix[k][i - 1]
                    now += val
                    ans += d[now - target]
                    d[now] += 1
        return ans

data = Solution()
matrix = [[0,1,0],[1,1,1],[0,1,0]]
target = 0
print(data.numSubmatrixSumTarget(matrix, target))